# -*- coding:utf-8 -*- 
__date__ = '2021/12/26 3:31 下午'

from util.list_util import random_list


def insertion_sort(collection):
    # 每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止
    length = len(collection)
    for right in range(1, length):
        target = collection[right]
        # 找到左边适合自己的位置
        for left in range(right):
            if collection[left] > target:
                # 插入target，后方的元素右移
                collection[left + 1:right + 1] = collection[left: right]
                collection[left] = target
                # 本轮插入完毕
                print(collection)
                break
    return collection


if __name__ == '__main__':
    random_list = random_list()
    print("random_list: ", random_list)
    res = insertion_sort(random_list)
    print(res)
